| RSA加密解密算法原理以及实现 | 您所在的位置：网站首页 › 欧拉定理 rsa加密 › RSA加密解密算法原理以及实现 |
RSA加密解密算法原理以及实现
|
文章目录
前言一、RSA加密算法是什么？加密过程1、选择一对不相等且足够大的质数2、计算p、q的乘积3、计算n的欧拉函数4、选择一个与
φ
(
n
)
\varphi(n)
φ(n)互质的整数e5、计算出e对于
φ
(
n
)
\varphi(n)
φ(n)的模反元素d6、将e、n公开作为公钥进行加密7、将d，n作为私钥进行解密
二、RSA算法使用c++语言实现时遇到的问题以及解决方案1.问题1：模反元素的求解问题2：大数的幂运算问题3：大数的加/减/乘/除/模运算问题4：大数产生随机数问题5：大数产生质数
三、RSA加密算法代码实现四、运行结果
前言
从古至今，如何用最有效的加密手段保护信息的安全性使之不被窃取、篡改或者破坏都是人们在信息传播中普遍关注的重大问题。最古老的文件加密手段莫过于对称加密，什么是对称加密，打个比方，有一个商人需要给合作伙伴送一批贵重的货物，他便将货物放在一个设置好密码的箱子中，这个密码只有商人知道，同时他又将设置好的密码提前告知合作伙伴，货物送达后，合作伙伴便可以用被告知的密码打开箱子取出货物。即用一种方法加密, 用同一种方法解密, 即为对称加密。对称加密从古至今都是比较广泛使用的一种加密方式，比如在宋朝就将代码法用于军事保密文件的传输，简而言之，比如双方约定某一本书，根据书中的字所在位子，比如“20页第2行第9个字”，破译的时候只要对照好，就能解码。如果不知道双方约定的解码书本，根本无法破解。这种方式现在还管用。比如在谍战片中，情报人员发出的电报，需要用对应的密码本来解译，如何密码本落入到地方手中，后果不堪设想。但是对称加密缺点在于，通过对称加密方法进行加密后，需要告知接收方加密方法才能解密，而将加密方法传输给接受方这一过程中，充满了各种泄密的可能。比如说在战争中，一旦密码本在传输的过程中被敌方截获，那么所有的电报内容都会被地方破解，以至于影响最终战争胜利的走向。所以，对称加密的安全性，最首先取决于加密方式的保密性，其次才是密码破译的难度。 如何能够消除了对称加密中用户交换密钥的需要的同时也能保证其保密性？因此，诞生的非对称加密。非对称加密算法需要两个密钥：公开密钥 (publickey:简称公钥) 和 私有密钥 (privatekey:简称私钥). 公钥与私钥是一 一对应的, 如果用公钥对数据进行加密, 只有用对应的私钥才能解密. 因为加密和解密使用的是两个不同的密钥, 所以这种算法叫作非对称加密算法. 基本过程为：甲方生成一对密钥与公钥, 并将公钥公开, 需要向甲方发送信息的其他角色(乙方, 丙方等) 使用甲方公开的公钥对机密信息进行加密后再发送给甲方. 甲方再用自己私钥对加密后的信息进行解密.甲方想要回复乙方时正好相反, 使用乙方公开的公钥对数据进行加密，同理，乙方使用自己的私钥来进行解密.本文中介绍非对称加密算法中的一种------RSA加密解密算法 一、RSA加密算法是什么？RSA是1977年由罗纳德·李维斯特（Ron Rivest）, 阿迪·萨莫尔（Adi Shamir）和 伦纳德·阿德曼（Leonard Adleman）一起提出的. 当时他们三人都在麻省理工学院工作. RSA就是他们三人姓氏开头字母拼在一起组成的.百度百科 加密过程 1、选择一对不相等且足够大的质数选择一对不相等且足够大的质数，我们将它描述为p和q。 2、计算p、q的乘积n=p*q 3、计算n的欧拉函数φ ( n ) = ( p − 1 ) ∗ ( q − 1 ) \varphi(n)=(p-1)*(q-1) φ(n)=(p−1)∗(q−1) 这个公式是如何得到的？那么就要从以下几个概念入手。 互质：如果两个整数的公约数只有1，此时它们叫做互质整数。 欧拉函数：欧拉函数是小于n的正整数中与n互质的数的数目。例如，与6互质且小于6的正整数有两个，分别是1和5，则 φ ( 6 ) = 2 \varphi(6)=2 φ(6)=2。如果n为质数，那么 φ ( n ) = n − 1 \varphi(n)=n-1 φ(n)=n−1，因为质数在大于1的自然数中，除了1和它本身以外不会再有其他因数的自然数。 此时如果n可以分解成2个互质的整数之积，那么n的欧拉函数等于这两个因子的欧拉函数之积。即若n=pq，且p、q互质，则 φ ( n ) = φ ( p ∗ q ) = φ ( p ) ∗ φ ( q ) \varphi(n)=\varphi(p*q)=\varphi(p)*\varphi(q) φ(n)=φ(p∗q)=φ(p)∗φ(q)=(p-1)(q-1)。 证明：p,2p,3p,…,(q−1)∗p有q−1个数整除pq，同理q,2q,3q,…,(p−1)∗q有p−1个数可以整除pq,再加上pq本身能整除pq,那么丢掉这些数剩余的数就与pq互质,一共有pq− (q−1+p−1+1) =(p−1)(q−1) 。 4、选择一个与 φ ( n ) \varphi(n) φ(n)互质的整数e10),这样就把求两个数的最大公约数转化为求两个更小的数的公约数，直到其中一个数为0，那么另一个数就是两者的最大公约数。 举个例子： F(42,30）=F（30,12）=F（12,6）=F（6,0）=6 但对于以上过过程，我们如何用代码去实现，我们先从公约数的特点入手。 设x= k 1 x 1 k_1x_1 k1x1，y= k 1 y 1 k_1y_1 k1y1，则F(x,y)= k 1 k_1 k1 F(x1,y1)。 设x=p x 1 x_1 x1，（p为素数且y%p!=0）则F(x,y)=F(x1,y)。 现在取p=2。 若x,y均为偶数，则F(x,y)=2F(x/2,y/2）。 若x为偶数，y为奇数则F(x,y)=F(x/2,y)。 若x为奇数，y为偶数则F(x,y)=F(x,y/2)。 若x和y同时为奇数，F(x,y)=F(y，x-y)。（两个奇数相减后必定会出现一个偶数） 这种做法的算法复杂度为O(log2(max(x,y)))。 #include #include #include using namespace std; int isoushu(long x) { if(x%2==0) return 1; else return 0; } int fun(long long a,long long b) { if(b>a) return fun(b,a); else if(a==0)return b; else { if(isoushu(a)) if(isoushu(b)) { return (fun(a>>1,b>>1)1,b); else { if(isoushu(b)) return fun(a,b>>1); else return (a-b,b); } } } main() { long long a,b; cin>>a>>b; cout ans=(ans*a)%c;//取余 } ans=ans%c;但是这个算法在时间复杂度上没有改进，仍为O(b)，不过已经好很多的，但是在c过大的条件下，还是很有可能超时，所以，我们需要用到快速幂算法来进行改进。 关于快速幂的算法的介绍，我么从推导其公式入手。 首先我们将十进制的指数b转换为2进制的形式
其中 a n a_n an代表对应对应第n位的二进制值，非0即1。那么由二进制转换为十进制的公式我们可以得到
此处的 a i a_i ai要么为0，要么为1，如果 a i a_i ai为0，那么这一项值就为1。所以可以再次将上述式子化简为
同时发现，对于每一项的计算时，计算后一项的结果时用前一项的结果的平方取余。用公式表示为
形如上式的公式推导，我们将其用代码实现。 int ans=1; a=a%c; while(b>0) { if(b%2==1) ans=(ans*a)%c; b=b/2; a=(a*a)%c; }此时，当b=0时，所有的因子都已经相乘，算法结束。于是便可以在O（log b）的时间内完成了。所以在进行模幂运算时, 运算的复杂度已经和指数b的大小没有直接关系了, 有直接关系的是b的二进制bit位数。 问题3：大数的加/减/乘/除/模运算在RSA算法中的数字极大, 是我们现有计算机无法直接计算的, 所以需要我们手动实现大数的加减乘除. 所以在实现中，直接调用boost库中的大数运算库cppp_int。 boost中的cpp_int库的介绍文档 https://www.boost.org/doc/libs/1_58_0/libs/multiprecision/doc/html/boost_multiprecision/tut/ints/cpp_int.html 项目使用的是boost_1_83_0版本的大数库,下载链接https://www.boost.org/users/download/ 在VS中还需要将解压好的boost库路径添加到附加目录, 步骤如下 我们平时用的随机数函数是 srand()设置随机数种子, 一般传入time(0), 用 rand()获取随机数, 随机数 = rand % num; 随机数范围是 [0, num). 在不同平台的不同编译器下rand()函数所能获取的随机数的范围不同, 但由于目前CPU位数的限制, 顶多也就是个64位的数字, 所以我们还需要能产生大随机数的方法. 解决方案：在boost库的random库中 有着大数随机数的获取方法，在调用时包含头文件#include 问题5：大数产生质数大数的素性检测有专门的算法, 比如fermat检测, Miller-Rabin等算法. 在boost库中的实现了Miller-Rabin素性检测算法,使用时添加头文件#include 三、RSA加密算法代码实现rsa.h #pragma once #include #include//大数库 #include//随机数库 #include//素性检测 #include //spilt()接口就在这个库中 namespace br = boost::random; namespace bm = boost::multiprecision; #define NUMBER 128 //临时缓冲区大小 #define SECRET_KEY_PATH "secret_key.txt" //存储N,D,E的文件名 #define SIZE 128 //控制随机数大小, 范围是 0 ~ 1 Key m_key; bm::int1024_t GetPrime(); bool isPrime(bm::int1024_t& num); bm::int1024_t getNkey(bm::int1024_t& prime1, bm::int1024_t& prime2);//获取公共模数n bm::int1024_t getOrla(bm::int1024_t& prime1, bm::int1024_t& prime2);//欧拉函数, 得到f(n) bm::int1024_t getEkey(bm::int1024_t& orla);//获取公钥 bm::int1024_t getDkey(bm::int1024_t& ekey, bm::int1024_t& orla);//获取私钥 void exGcd(bm::int1024_t a, bm::int1024_t b, bm::int1024_t* x, bm::int1024_t* y);//求模反元素 bm::int1024_t getGcd(bm::int1024_t num1, bm::int1024_t num2);//最大公约数 bm::int1024_t _encrypt(bm::int1024_t data, bm::int1024_t ekey, bm::int1024_t nkey);//加密,需要加密数据和公钥(e, n) bm::int1024_t _decrypt(bm::int1024_t data, bm::int1024_t dkey, bm::int1024_t nkey);//解密,需要要解密的数据和私钥(d, n) void getKeys(); public: RSA(); bool encrypt(const std::string filename, const std::string outname);//加密 bool decrypt(const std::string filename, const std::string outname);//解密 };rsa.cpp #include #include #include"rsa.h" using namespace std; RSA::RSA() { getKeys(); } bm::int1024_t RSA::getNkey(bm::int1024_t& prime1, bm::int1024_t& prime2) { return prime1 * prime2; } bm::int1024_t RSA::getOrla(bm::int1024_t& prime1, bm::int1024_t& prime2) {//prime1和prime2必须互质 return (prime1 - 1) * (prime2 - 1); } bm::int1024_t RSA::getEkey(bm::int1024_t& orla) { bm::int1024_t ekey; br::mt11213b gen((size_t)time(0)); br::uniform_int_distribution dist(bm::int1024_t(0), (bm::int1024_t(orla))); do { ekey = dist(gen); } while (ekey bm::int1024_t num; while ((num = num1 % num2)) { num1 = num2; num2 = num; } return num2; } void RSA::exGcd(bm::int1024_t a, bm::int1024_t b, bm::int1024_t* x, bm::int1024_t* y) { if (b == 0) { *x = 1; *y = 0; return; } exGcd(b, a % b, x, y); bm::int1024_t tmp = *x; *x = *y; *y = tmp - a / b * (*y); } bm::int1024_t RSA::_encrypt(bm::int1024_t Ai, bm::int1024_t ekey, bm::int1024_t nkey) { //data^ekey % nkey //只和ekey的位数有关 bm::int1024_t res = 1; for (; ekey; ekey >>= 1) { if (ekey & 1) { res = (res*Ai) % nkey; } Ai = (Ai*Ai) % nkey; } return res; } bm::int1024_t RSA::_decrypt(bm::int1024_t data, bm::int1024_t dkey, bm::int1024_t nkey) { return _encrypt(data, dkey, nkey); } bool RSA::isPrime(bm::int1024_t& num) { br::mt11213b gen((size_t)time(0));//要和产生随机数的发生器不一样 if (miller_rabin_test(num, 25, gen)) { if (miller_rabin_test((num - 1) / 2, 25, gen)) { return true; } } return false; } bm::int1024_t RSA::GetPrime() { bm::int1024_t res; br::mt19937 gen((size_t)time(0)); br::uniform_int_distribution dist(bm::int1024_t(0), (bm::int1024_t(1) cout cout perror("file open failed!"); return; } string buf; buf.resize(fsize); fin.read(&buf[0], fsize); if (fin.good() == false) { cout perror("input file open failed!"); return false; } char* buffer = new char[NUMBER]; bm::int1024_t* bufferOut = new bm::int1024_t[NUMBER]; while (!fin.eof()) { fin.read(buffer, NUMBER); streamsize ret = fin.gcount(); for (streamsize i = 0; i ifstream fin(filename, ifstream::binary); ofstream fout(outname, ifstream::binary); if (!fin.is_open()) { perror("file open failed"); return false; } bm::int1024_t* buffer = new bm::int1024_t[NUMBER]; char* bufferOut = new char[NUMBER]; while (!fin.eof()) { fin.read((char*)buffer, NUMBER * sizeof(bm::int1024_t)); streamsize ret = fin.gcount() / sizeof(bm::int1024_t); for (streamsize i = 0; i RSA rsa; if (rsa.encrypt(filename, EncName)) { cout string filename("明文.txt"), EncName("密文.txt"), DecName("解密后的文件.txt"); Test(filename, EncName, DecName); return 0; } 四、运行结果明文 密文 |
化简上述公式可得 
则
a
b
a^b
abmod c可重写为
其中
k
i
k_i
ki表示
a
i
a_i
ai不为0的项。
解密后的文件 
【本文地址】